<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>单向链表</title>
  </head>
  <body>
    <script type="text/javascript">
      // 封装链表类
      function LinkedList() {
        // 创建节点类
        function Node(data) {
          this.data = data
          this.next = null
        }
        //属性
        this.head = null
        this.length = 0

        // 1.链表尾部追加元素方法
        LinkedList.prototype.append = function(data) {
          // 1.根据新元素创建节点
          let newNode = new Node(data)
          // 2.判断原来链表是否为空
          if (this.head === null) { // 链表尾空
            this.head = newNode
          } else { // 链表不为空
            // 2.1.定义变量, 保存当前找到的节点
            let current = this.head
            while (current.next) {
              current = current.next
            }
            // 2.2.找到最后一项, 将其next赋值为node
            current.next = newNode
          }
          // 3.链表长度增加1
          this.length++
        }
        // 2.链表的toString方法
        LinkedList.prototype.toString = function() {
          // 1.定义两个变量
          let current = this.head
          let listString = ""
          // 2.循环获取链表中所有的元素
          while (current) {
            listString += "," + current.data
            current = current.next
          }
          // 3.返回最终结果,this.head为空
          return listString.slice(1)
        }
        // 3.insert方法
        LinkedList.prototype.insert = function(position, data) {
          // 1.对position进行越界处理
          if (position < 0 || position > this.length) return false
          // 2.创建新的节点
          let newNode = new Node(data)
          // 3.判断插入的位置是不是第一个节点
          let current = this.head
          let previous = null
          let index = 0
          if (position == 0) {
            newNode.next = current
            this.head = newNode
          } else {
            while (index++ < position) {
              previous = current
              current = current.next
            }
            newNode.next = current
            previous.next = newNode
          }
          // length +1
          this.length += 1
          return true
        }
        //4.get方法根据索引获取数据
        LinkedList.prototype.get = function(position) {
          // 1.对position进行越界处理
          if (position < 0 || position >= this.length) return null
          // 2.获取data
          let current = this.head
          let index = 0
          while (index++ < position) {
            current = current.next
          }
          return current.data
        }
        //5.indexOf方法根据数据获取索引
        LinkedList.prototype.indexOf = function(data) {
          // 1.定义变量
          let current = this.head
          let index = 0
          //2.开始查找
          while (current) {
            if (current.data === data) {
              return index
            } else {
              current = current.next
              index += 1
            }
          }
          // 3.未查找到
          return -1
        }
        //6.update方法
        LinkedList.prototype.update = function(position, newdata) {
          // 1.对position进行越界处理
          if (position < 0 || position >= this.length) return false
          // 2.查找正确的节点
          let current = this.head
          let index = 0
          while (index++ < position) {
            current = current.next
          }
          // 修改data
          current.data = newdata
          return true
        }
        //7.removeAt方法
        LinkedList.prototype.removeAt = function(position) {
          // 1.对position进行越界处理
          if (position < 0 || position >= this.length) return null
          // 判断是不是删除的是第一个值
          let current = this.head
          let previous = null
          let index = 0
          if (position == 0) {
            this.head = current.next
          } else {
            while (index++ < position) {
              previous = current
              current = current.next
            }
            previous.next = current.next
          }

          // 3.length -1
          length -= 1

          return current.data
        }
        //8.remove方法
        LinkedList.prototype.remove = function(data) {
          // 1.获取位置信息
          let position = this.indexOf(data)
          // 2.根据位置删除信息
          return this.removeAt(position)
        }
        //9.isEmpty方法
        LinkedList.prototype.isEmpty = function() {
          return this.length == 0
        }
        //10.size方法
        LinkedList.prototype.size = function() {
          return this.length
        }
      }
      // 测试代码
      // 测试链表
      // 1.创建链表
      let list = new LinkedList()

      // 2.追加元素
      list.append(15)
      list.append(10)
      list.append(20)

      // 3.打印链表的结果
      alert(list)
      console.log(list);

      //测试insert方法
      list.insert(0, 100)
      list.insert(2, 300)
      list.insert(4, 200)
      alert(list)
      console.log(list)
      //测试get方法
      alert(list.get(0))
      alert(list.get(1))
      //测试indexOf方法
      console.log(list.indexOf("as"))
      console.log(list.indexOf(300))
      console.log(list.indexOf(200))
      //测试update方法
      list.indexOf(0, "as")
      list.indexOf(2, 300)
      list.indexOf(3, 200)
      alert(list)
      console.log(list)
      //测试removeAt方法
      console.log(list.removeAt(0))
      alert(list)
      console.log(list)
      //测试remove方法
      console.log(list.remove(300))
      //测试isEmpty方法
      console.log(list.isEmpty())
      //测试size方法
      console.log(list.size())
      alert(list)
    </script>
  </body>
</html>
